package com.maduar.demo.algo;

/**
 * Description:
 *
 * @author danny.pang danny.pang@ebizprise.com
 * @date 2020-07-21 00:49
 */
public class BSTree<T extends Comparable> {

    private Node<T> root;

    public void insert(T data) {
        Node<T> newNode = new Node<>();
        newNode.key = data;

        if (root == null) {
            root = newNode;
        } else {
            Node<T> current = root;
            Node<T> parent;

            while (true) {
                parent = current;
                if (data.compareTo(current.key) < 0) {
                    current = current.left;
                    if (current == null) {
                        parent.left = newNode;
                        return;
                    }
                } else {
                    current = current.right;
                    if (current == null) {
                        parent.right = newNode;
                        return;
                    }
                }
            }
        }
    }

    public void preOrder() {
        preOrder(root);
    }

    private void preOrder(Node<T> tree) {
        if (tree != null) {
            System.out.print(tree.key + " ");
            preOrder(tree.left);
            preOrder(tree.right);
        }
    }

    public void inOrder() {
        inOrder(root);
    }

    private void inOrder(Node<T> tree) {
        if (tree != null) {
            preOrder(tree.left);
            System.out.print(tree.key + " ");
            preOrder(tree.right);
        }
    }

    public static void main(String[] args) {
        BSTree<String> tree = new BSTree<>();

        tree.insert("A");
        tree.insert("B");
        tree.insert("D");
        tree.insert("E");
        tree.insert("C");
        tree.insert("F");
        tree.insert("G");
        tree.insert("H");

        tree.preOrder();
        System.out.println();
        System.out.println("--------");

        tree.inOrder();
    }
}
